home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 4 / CDPD_IV.bin / e / mailinglists / amigae.0793july.archive / 000019_crash!minyos.xx….OZ.AU!s924723_Sat, 10 Jul 93 09:40:54 PST.msg < prev    next >
Internet Message Format  |  1994-05-26  |  5KB
  1. Received: by bkhouse.cts.com (V1.16/Amiga)
  2.     id AA00000; Sat, 10 Jul 93 09:40:54 PST
  3. Received: from peladon.rmit.OZ.AU by crash.cts.com with smtp
  4.     (Smail3.1.28.1 #15) id m0oEgKX-0000DuC; Sat, 10 Jul 93 07:55 PDT
  5. Received: from minyos.xx.rmit.OZ.AU by peladon.rmit.OZ.AU with SMTP id AA05244
  6.   (5.65c/IDA-1.4.4 for <amigae@bkhouse.cts.com>); Sun, 11 Jul 1993 00:55:07 +1000
  7. Received: by minyos.xx.rmit.OZ.AU
  8. Message-Id: <9307101455.11858@minyos.xx.rmit.OZ.AU>
  9. Date: Sun, 11 Jul 1993 00:55:07 +1000 (EST)
  10. X-Mailer: ELM [version 2.4 PL22]
  11. Mime-Version: 1.0
  12. Content-Type: text/plain; charset=US-ASCII
  13. Content-Transfer-Encoding: 7bit
  14. Content-Length: 3652
  15. From: s924723@minyos.xx.rmit.OZ.AU (Son Huu Le)
  16. To: amigae@bkhouse.cts.com
  17. Subject: Slow E example
  18.  
  19. Forwarded message:
  20.  From MAILER-DAEMON Sat Jul 10 12:16:53 1993
  21. Date: Sat, 10 Jul 93 12:16:30 EST
  22. From: MAILER-DAEMON (Mail Delivery Subsystem)
  23. Subject: Returned mail: Service unavailable
  24. Message-Id: <9307100216.24669@minyos.xx.rmit.OZ.AU>
  25. To: s924723
  26.  
  27.    ----- Transcript of session follows -----
  28. >>> DATA
  29. <<< 554 <Wouter@alt.let.uva.nl>... 550 Host unknown (Authoritative answer from name server)
  30. 554 Wouter@alt.let.uva.nl... Service unavailable
  31.  
  32.    ----- Unsent message follows -----
  33. Received: by minyos.xx.rmit.OZ.AU 
  34. Date: Sat, 10 Jul 93 12:16:30 EST
  35. From: s924723 (Son Huu Le)
  36. Message-Id: <9307100216.24669@minyos.xx.rmit.OZ.AU>
  37. To: Wouter@alt.let.uva.nl
  38. Subject: Slow_E
  39.  
  40.  
  41. Okay. Here's the slow E port of boyerm.c - It's been stripped of the
  42. non-essential routines and has a few features hard-coded (laziness, I know :)
  43. Basically it searches my Aminet catalogue for Toolmanager2.0 (there's only
  44. one entry) using Boyer-Moore string search. I compiled practically the same
  45. code in C format (of coz) using SAS/C v6.3 and the results were something
  46. like 30secs for SAS/C and 60 secs for E.
  47.  
  48. Any help much appreciated.
  49.  
  50. Son Le
  51.  
  52. PS. Another idea would be to include a set of standard functions with E for
  53. basic functions like atoi, islower, etc. And also about the .o files, how
  54. about mimicking c.o with e.o?
  55.  
  56. /* boyerm - find lines containing given constant string       */
  57. /* A. Kotanski, 1989                                          */
  58. /* For explanation of the method see the following articles : */
  59. /* R.S.Boyer, J.S. Moore, "A fast string search algorithm"    */
  60. /*                        Comm. ACM 20, 762-772 (1977)        */
  61. /* D.E.Knuth, J.H.Morris and V.B.Pratt                        */
  62. /*                        "Fast pattern matching in strings"  */
  63. /*                        SIAM J. Computing, 6, 323-350 (1977)*/
  64.  
  65. CONST UPPER=255
  66.  
  67. DEF except = 0, number = 0, ppos = 1, patlen, stringlen, c,
  68.     delta0[128]:STRING, delta2[80]:STRING, string[256]:STRING,
  69.     pat[80]:STRING, f[80]:STRING
  70.  
  71. PROC max(a,b) RETURN (IF a>b THEN a ELSE b)
  72. PROC min(a,b) RETURN (IF a>b THEN b ELSE a)
  73.  
  74. PROC boyer()
  75. DEF i, j
  76.  
  77.    IF ( (i := patlen + ppos - 2) >= stringlen ) THEN RETURN 0
  78.    LOOP
  79.       WHILE ( (i := i + delta0[string[i]]) < stringlen ) DO NOP
  80.       IF ( i < UPPER ) THEN RETURN 0
  81.       i := i - (UPPER + 1)
  82.       IF ( (j := patlen - 2) < 0 ) THEN RETURN (i + 2)
  83.       WHILE ( string[i] = pat[j] )
  84.          i--
  85.          IF ( j-- < 0 ) THEN RETURN (i + 2)
  86.       ENDWHILE
  87.       IF ( string[i] = pat[patlen-1] )
  88.          i := i + delta2[j]
  89.       ELSE
  90.          i := i + max(delta0[string[i]], delta2[j])
  91.       ENDIF
  92.       IF CtrlC()=TRUE THEN Raise(0)
  93.    ENDLOOP
  94. ENDPROC
  95.  
  96. PROC main() HANDLE  /* find pattern from first argument */
  97. DEF lineno = 0, match, i, t, fh
  98.  
  99.    IF (fh := Open (arg,OLDFILE))=NIL
  100.       WriteF('Open error\n')
  101.       CleanUp(0)
  102.    ENDIF
  103.    StrCopy(pat,'ToolManager2.0',ALL)
  104.  
  105.    patlen := StrLen(pat)
  106.  
  107.    FOR i := 0 TO 127 DO delta0[i] := patlen
  108.    FOR i := 0 TO patlen-1 DO delta0[pat[i]] := patlen - i - 1
  109.  
  110.    delta0[pat[patlen - 1]] := UPPER
  111.  
  112.    FOR i := 0 TO patlen-1 DO delta2[i] := patlen + patlen - i - 1
  113.  
  114.    i := patlen - 1
  115.    t := patlen
  116.    WHILE ( i >= 0 )
  117.       f[i] := t
  118.       WHILE ( ( t < patlen ) AND ( pat[i] <> pat[t] ) ) 
  119.          delta2[t] := min(delta2[t], patlen-i-1)
  120.          t := f[t]
  121.       ENDWHILE
  122.       t--
  123.       i--
  124.    ENDWHILE
  125.    FOR i := 0 TO t DO delta2[i] := min(delta2[i], patlen + t - i)
  126.  
  127.    WHILE Fgets(fh, string, 256)
  128.       lineno++
  129.       stringlen := StrLen(string)
  130.       match := boyer()
  131.       IF match THEN WriteF('\s',string)
  132.    ENDWHILE
  133.    Raise(0)
  134. EXCEPT
  135.    IF fh THEN Close(fh)
  136. ENDPROC
  137.  
  138.